In a data switching network, data traffic is categorized into various flows which are stored in a number of virtual queues in a buffer. In a router or other network element, the stored queues typically compete for a common outgoing communications link or egress port (e.g., a physical communications link or a pseudo-wire). Thus, the buffered queues need to be scheduled on the egress side. Accordingly, a packet scheduling process is performed in the router to select which of the queued packets will be the next in line for outgoing transmission.
Typically, in a routing process, data packets coming in from different source ports are classified based on their source and destination ports and traffic types. They are subsequently sorted into different queues in the buffer. The state of each queue is updated when a packet enters into a queue. Based on the output port availability, the scheduler selects the right scheduling algorithm to dequeue the packets from the corresponding queues. The state of each queue will be updated when a packet moves out of a queue. The winner of each scheduling stage is recorded and considered for fairness in the next scheduling iteration.
Data transmission congestion possibly occurs due to oversubscription of an egress port, a limited transmission rate, or an unavailable or unready downstream receiving device, etc. In these scenarios, a scheduling process needs to provide traffic management, use fairness and service differentiation. For example, Quality of Service (QoS) algorithms are used to guarantee a preferential service for the high priority traffic, such as control traffic or voice/video latency sensitive traffic.
Conventionally, a scheduling process merely evaluates the state of the buffered queues to determine the order of allocating data packets to selected egress ports for transmission. This provides a single and fixed level of control granularity to achieve service differentiation or other desired features. Unfortunately, it lacks the ability of controlling QoS in other levels of granularities (e.g., based on Internet service provider, business entities, and user groups, etc.).